home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / THINKC / 4_0 / FLEX-TC_ / NFA.C < prev    next >
Text File  |  1990-01-03  |  17KB  |  721 lines
  1. /* nfa - NFA construction routines */
  2.  
  3. /*
  4.  * Copyright (c) 1989 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  *
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that the above copyright notice and this paragraph are
  16.  * duplicated in all such forms and that any documentation,
  17.  * advertising materials, and other materials related to such
  18.  * distribution and use acknowledge that the software was developed
  19.  * by the University of California, Berkeley.  The name of the
  20.  * University may not be used to endorse or promote products derived
  21.  * from this software without specific prior written permission.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  */
  26.  
  27. #ifndef lint
  28.  
  29. static char copyright[] =
  30. "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
  31. static char CR_continuation[] = "@(#) All rights reserved.\n";
  32.  
  33. static char rcsid[] =
  34. "@(#) $Header: nfa.c,v 2.0 89/06/20 15:50:05 vern Locked $ (LBL)";
  35.  
  36. #endif
  37.  
  38. #include "flexdef.h"
  39.  
  40. /* add_accept - add an accepting state to a machine
  41.  *
  42.  * synopsis
  43.  *
  44.  *     add_accept( mach, accepting_number );
  45.  *
  46.  * accepting_number becomes mach's accepting number.
  47.  */
  48.  
  49. add_accept( mach, accepting_number )
  50. int mach;
  51.  
  52. {
  53.     /* hang the accepting number off an epsilon state.    if it is associated
  54.      * with a state that has a non-epsilon out-transition, then the state
  55.      * will accept BEFORE it makes that transition, i.e., one character
  56.      * too soon
  57.      */
  58.  
  59.     if ( transchar[finalst[mach]] == SYM_EPSILON )
  60.         accptnum[finalst[mach]] = accepting_number;
  61.  
  62.     else
  63.     {
  64.         int astate = mkstate( SYM_EPSILON );
  65.         accptnum[astate] = accepting_number;
  66.         mach = link_machines( mach, astate );
  67.     }
  68. }
  69.  
  70.  
  71. /* copysingl - make a given number of copies of a singleton machine
  72.  *
  73.  * synopsis
  74.  *
  75.  *     newsng = copysingl( singl, num );
  76.  *
  77.  *       newsng - a new singleton composed of num copies of singl
  78.  *       singl  - a singleton machine
  79.  *       num      - the number of copies of singl to be present in newsng
  80.  */
  81.  
  82. int copysingl( singl, num )
  83. int singl, num;
  84.  
  85. {
  86.     int copy, i;
  87.  
  88.     copy = mkstate( SYM_EPSILON );
  89.  
  90.     for ( i = 1; i <= num; ++i )
  91.         copy = link_machines( copy, dupmachine( singl ) );
  92.  
  93.     return ( copy );
  94. }
  95.  
  96.  
  97. /* dumpnfa - debugging routine to write out an nfa
  98.  *
  99.  * synopsis
  100.  *      int state1;
  101.  *      dumpnfa( state1 );
  102.  */
  103.  
  104. dumpnfa( state1 )
  105. int state1;
  106.  
  107. {
  108.     int sym, tsp1, tsp2, anum, ns;
  109.  
  110.     fprintf( stderr, "\n\n********** beginning dump of nfa with start state %d\n",
  111.     state1 );
  112.  
  113.     /* we probably should loop starting at firstst[state1] and going to
  114.      * lastst[state1], but they're not maintained properly when we "or"
  115.      * all of the rules together.  So we use our knowledge that the machine
  116.      * starts at state 1 and ends at lastnfa.
  117.      */
  118.  
  119.     /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  120.     for ( ns = 1; ns <= lastnfa; ++ns )
  121.     {
  122.         fprintf( stderr, "state # %4d\t", ns );
  123.  
  124.         sym = transchar[ns];
  125.         tsp1 = trans1[ns];
  126.         tsp2 = trans2[ns];
  127.         anum = accptnum[ns];
  128.  
  129.         fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
  130.  
  131.         if ( anum != NIL )
  132.             fprintf( stderr, "  [%d]", anum );
  133.  
  134.         fprintf( stderr, "\n" );
  135.     }
  136.  
  137.     fprintf( stderr, "********** end of dump\n" );
  138. }
  139.  
  140.  
  141. /* dupmachine - make a duplicate of a given machine
  142.  *
  143.  * synopsis
  144.  *
  145.  *     copy = dupmachine( mach );
  146.  *
  147.  *       copy - holds duplicate of mach
  148.  *       mach - machine to be duplicated
  149.  *
  150.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  151.  * transition states values are adjusted so that the copy is self-contained,
  152.  * as the original should have been.
  153.  *
  154.  * also note that the original MUST be contiguous, with its low and high
  155.  * states accessible by the arrays firstst and lastst
  156.  */
  157.  
  158. int dupmachine( mach )
  159. int mach;
  160.  
  161. {
  162.     int i, init, state_offset;
  163.     int state = 0;
  164.     int last = lastst[mach];
  165.  
  166.     for ( i = firstst[mach]; i <= last; ++i )
  167.     {
  168.         state = mkstate( transchar[i] );
  169.  
  170.         if ( trans1[i] != NO_TRANSITION )
  171.         {
  172.             mkxtion( finalst[state], trans1[i] + state - i );
  173.  
  174.             if ( transchar[i] == SYM_EPSILON && trans2[i] != NO_TRANSITION )
  175.                 mkxtion( finalst[state], trans2[i] + state - i );
  176.         }
  177.  
  178.         accptnum[state] = accptnum[i];
  179.     }
  180.  
  181.     if ( state == 0 )
  182.         flexfatal( "empty machine in dupmachine()" );
  183.  
  184.     state_offset = state - i + 1;
  185.  
  186.     init = mach + state_offset;
  187.     firstst[init] = firstst[mach] + state_offset;
  188.     finalst[init] = finalst[mach] + state_offset;
  189.     lastst[init] = lastst[mach] + state_offset;
  190.  
  191.     return ( init );
  192. }
  193.  
  194. /* finish_rule - finish up the processing for a rule
  195.  *
  196.  * synopsis
  197.  *
  198.  *     finish_rule( mach, variable_trail_rule, headcnt, trailcnt );
  199.  *
  200.  * An accepting number is added to the given machine.  If variable_trail_rule
  201.  * is true then the rule has trailing context and both the head and trail
  202.  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
  203.  * the machine recognizes a pattern with trailing context and headcnt is
  204.  * the number of characters in the matched part of the pattern, or zero
  205.  * if the matched part has variable length.  trailcnt is the number of
  206.  * trailing context characters in the pattern, or zero if the trailing
  207.  * context has variable length.
  208.  */
  209.  
  210. finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
  211. int mach, variable_trail_rule, headcnt, trailcnt;
  212.  
  213. {
  214.     add_accept( mach, num_rules );
  215.  
  216.     /* we did this in new_rule(), but it often gets the wrong
  217.      * number because we do it before we start parsing the current rule
  218.      */
  219.     rule_linenum[num_rules] = linenum;
  220.  
  221.     fprintf( temp_action_file, "case %d:\n", num_rules );
  222.  
  223.     if ( variable_trail_rule )
  224.     {
  225.         rule_type[num_rules] = RULE_VARIABLE;
  226.  
  227.         if ( performance_report )
  228.             fprintf( stderr, "Variable trailing context rule at line %d\n",
  229.             rule_linenum[num_rules] );
  230.  
  231.         variable_trailing_context_rules = true;
  232.     }
  233.  
  234.     else
  235.     {
  236.         rule_type[num_rules] = RULE_NORMAL;
  237.  
  238.         if ( headcnt > 0 || trailcnt > 0 )
  239.         {
  240.             /* do trailing context magic to not match the trailing characters */
  241.             char *scanner_cp = "yy_c_buf_p = yy_cp";
  242.             char *scanner_bp = "yy_bp";
  243.  
  244.             fprintf( temp_action_file,
  245.             "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
  246.  
  247.             if ( headcnt > 0 )
  248.             {
  249.                 if ( headcnt > 0 )
  250.                     fprintf( temp_action_file, "%s = %s + %d;\n",
  251.                     scanner_cp, scanner_bp, headcnt );
  252.  
  253.                 else
  254.                     fprintf( temp_action_file, "%s = %s;\n",
  255.                     scanner_cp, scanner_bp );
  256.             }
  257.  
  258.             else
  259.                 fprintf( temp_action_file,
  260.                 "%s -= %d;\n", scanner_cp, trailcnt );
  261.  
  262.             fprintf( temp_action_file,
  263.             "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  264.         }
  265.     }
  266.  
  267.     line_directive_out( temp_action_file );
  268. }
  269.  
  270.  
  271. /* link_machines - connect two machines together
  272.  *
  273.  * synopsis
  274.  *
  275.  *     new = link_machines( first, last );
  276.  *
  277.  *       new      - a machine constructed by connecting first to last
  278.  *       first  - the machine whose successor is to be last
  279.  *       last   - the machine whose predecessor is to be first
  280.  *
  281.  * note: this routine concatenates the machine first with the machine
  282.  *    last to produce a machine new which will pattern-match first first
  283.  *    and then last, and will fail if either of the sub-patterns fails.
  284.  *    FIRST is set to new by the operation.  last is unmolested.
  285.  */
  286.  
  287. int link_machines( first, last )
  288. int first, last;
  289.  
  290. {
  291.     if ( first == NIL )
  292.         return ( last );
  293.  
  294.     else
  295.         if ( last == NIL )
  296.             return ( first );
  297.  
  298.     else
  299.     {
  300.         mkxtion( finalst[first], last );
  301.         finalst[first] = finalst[last];
  302.         lastst[first] = max( lastst[first], lastst[last] );
  303.         firstst[first] = min( firstst[first], firstst[last] );
  304.  
  305.         return ( first );
  306.     }
  307. }
  308.  
  309.  
  310. /* mark_beginning_as_normal - mark each "beginning" state in a machine
  311.  *                              as being a "normal" (i.e., not trailing context-
  312.  *                              associated) states
  313.  *
  314.  * synopsis
  315.  *
  316.  *     mark_beginning_as_normal( mach )
  317.  *
  318.  *       mach - machine to mark
  319.  *
  320.  * The "beginning" states are the epsilon closure of the first state
  321.  */
  322.  
  323. mark_beginning_as_normal( mach )
  324. register int mach;
  325.  
  326. {
  327.     switch ( state_type[mach] )
  328.     {
  329.         case STATE_NORMAL:
  330.             /* oh, we've already visited here */
  331.             return;
  332.  
  333.         case STATE_TRAILING_CONTEXT:
  334.             state_type[mach] = STATE_NORMAL;
  335.  
  336.             if ( transchar[mach] == SYM_EPSILON )
  337.             {
  338.                 if ( trans1[mach] != NO_TRANSITION )
  339.                     mark_beginning_as_normal( trans1[mach] );
  340.  
  341.                 if ( trans2[mach] != NO_TRANSITION )
  342.                     mark_beginning_as_normal( trans2[mach] );
  343.             }
  344.             break;
  345.  
  346.         default:
  347.             flexerror( "bad state type in mark_beginning_as_normal()" );
  348.             break;
  349.     }
  350. }
  351.  
  352.  
  353. /* mkbranch - make a machine that branches to two machines
  354.  *
  355.  * synopsis
  356.  *
  357.  *     branch = mkbranch( first, second );
  358.  *
  359.  *       branch - a machine which matches either first's pattern or second's
  360.  *       first, second - machines whose patterns are to be or'ed (the | operator)
  361.  *
  362.  * note that first and second are NEITHER destroyed by the operation.  Also,
  363.  * the resulting machine CANNOT be used with any other "mk" operation except
  364.  * more mkbranch's.  Compare with mkor()
  365.  */
  366.  
  367. int mkbranch( first, second )
  368. int first, second;
  369.  
  370. {
  371.     int eps;
  372.  
  373.     if ( first == NO_TRANSITION )
  374.         return ( second );
  375.  
  376.     else
  377.         if ( second == NO_TRANSITION )
  378.             return ( first );
  379.  
  380.     eps = mkstate( SYM_EPSILON );
  381.  
  382.     mkxtion( eps, first );
  383.     mkxtion( eps, second );
  384.  
  385.     return ( eps );
  386. }
  387.  
  388.  
  389. /* mkclos - convert a machine into a closure
  390.  *
  391.  * synopsis
  392.  *     new = mkclos( state );
  393.  *
  394.  *       new - a new state which matches the closure of "state"
  395.  */
  396.  
  397. int mkclos( state )
  398. int state;
  399.  
  400. {
  401.     return ( mkopt( mkposcl( state ) ) );
  402. }
  403.  
  404.  
  405. /* mkopt - make a machine optional
  406.  *
  407.  * synopsis
  408.  *
  409.  *     new = mkopt( mach );
  410.  *
  411.  *       new    - a machine which optionally matches whatever mach matched
  412.  *       mach - the machine to make optional
  413.  *
  414.  * notes:
  415.  *       1. mach must be the last machine created
  416.  *       2. mach is destroyed by the call
  417.  */
  418.  
  419. int mkopt( mach )
  420. int mach;
  421.  
  422. {
  423.     int eps;
  424.  
  425.     if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
  426.     {
  427.         eps = mkstate( SYM_EPSILON );
  428.         mach = link_machines( mach, eps );
  429.     }
  430.  
  431.     /* can't skimp on the following if FREE_EPSILON(mach) is true because
  432.      * some state interior to "mach" might point back to the beginning
  433.      * for a closure
  434.      */
  435.     eps = mkstate( SYM_EPSILON );
  436.     mach = link_machines( eps, mach );
  437.  
  438.     mkxtion( mach, finalst[mach] );
  439.  
  440.     return ( mach );
  441. }
  442.  
  443.  
  444. /* mkor - make a machine that matches either one of two machines
  445.  *
  446.  * synopsis
  447.  *
  448.  *     new = mkor( first, second );
  449.  *
  450.  *       new - a machine which matches either first's pattern or second's
  451.  *       first, second - machines whose patterns are to be or'ed (the | operator)
  452.  *
  453.  * note that first and second are both destroyed by the operation
  454.  * the code is rather convoluted because an attempt is made to minimize
  455.  * the number of epsilon states needed
  456.  */
  457.  
  458. int mkor( first, second )
  459. int first, second;
  460.  
  461. {
  462.     int eps, orend;
  463.  
  464.     if ( first == NIL )
  465.         return ( second );
  466.  
  467.     else
  468.         if ( second == NIL )
  469.             return ( first );
  470.  
  471.     else
  472.     {
  473.         /* see comment in mkopt() about why we can't use the first state
  474.          * of "first" or "second" if they satisfy "FREE_EPSILON"
  475.          */
  476.         eps = mkstate( SYM_EPSILON );
  477.  
  478.         first = link_machines( eps, first );
  479.  
  480.         mkxtion( first, second );
  481.  
  482.         if ( SUPER_FREE_EPSILON(finalst[first]) &&
  483.             accptnum[finalst[first]] == NIL )
  484.         {
  485.             orend = finalst[first];
  486.             mkxtion( finalst[second], orend );
  487.         }
  488.  
  489.         else
  490.             if ( SUPER_FREE_EPSILON(finalst[second]) &&
  491.                 accptnum[finalst[second]] == NIL )
  492.             {
  493.                 orend = finalst[second];
  494.                 mkxtion( finalst[first], orend );
  495.             }
  496.  
  497.         else
  498.         {
  499.             eps = mkstate( SYM_EPSILON );
  500.  
  501.             first = link_machines( first, eps );
  502.             orend = finalst[first];
  503.  
  504.             mkxtion( finalst[second], orend );
  505.         }
  506.     }
  507.  
  508.     finalst[first] = orend;
  509.     return ( first );
  510. }
  511.  
  512.  
  513. /* mkposcl - convert a machine into a positive closure
  514.  *
  515.  * synopsis
  516.  *     new = mkposcl( state );
  517.  *
  518.  *      new - a machine matching the positive closure of "state"
  519.  */
  520.  
  521. int mkposcl( state )
  522. int state;
  523.  
  524. {
  525.     int eps;
  526.  
  527.     if ( SUPER_FREE_EPSILON(finalst[state]) )
  528.     {
  529.         mkxtion( finalst[state], state );
  530.         return ( state );
  531.     }
  532.  
  533.     else
  534.     {
  535.         eps = mkstate( SYM_EPSILON );
  536.         mkxtion( eps, state );
  537.         return ( link_machines( state, eps ) );
  538.     }
  539. }
  540.  
  541.  
  542. /* mkrep - make a replicated machine
  543.  *
  544.  * synopsis
  545.  *     new = mkrep( mach, lb, ub );
  546.  *
  547.  *      new - a machine that matches whatever "mach" matched from "lb"
  548.  *            number of times to "ub" number of times
  549.  *
  550.  * note
  551.  *     if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
  552.  */
  553.  
  554. int mkrep( mach, lb, ub )
  555. int mach, lb, ub;
  556.  
  557. {
  558.     int base_mach, tail, copy, i;
  559.  
  560.     base_mach = copysingl( mach, lb - 1 );
  561.  
  562.     if ( ub == INFINITY )
  563.     {
  564.         copy = dupmachine( mach );
  565.         mach = link_machines( mach,
  566.         link_machines( base_mach, mkclos( copy ) ) );
  567.     }
  568.  
  569.     else
  570.     {
  571.         tail = mkstate( SYM_EPSILON );
  572.  
  573.         for ( i = lb; i < ub; ++i )
  574.         {
  575.             copy = dupmachine( mach );
  576.             tail = mkopt( link_machines( copy, tail ) );
  577.         }
  578.  
  579.         mach = link_machines( mach, link_machines( base_mach, tail ) );
  580.     }
  581.  
  582.     return ( mach );
  583. }
  584.  
  585.  
  586. /* mkstate - create a state with a transition on a given symbol
  587.  *
  588.  * synopsis
  589.  *
  590.  *     state = mkstate( sym );
  591.  *
  592.  *       state - a new state matching sym
  593.  *       sym     - the symbol the new state is to have an out-transition on
  594.  *
  595.  * note that this routine makes new states in ascending order through the
  596.  * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
  597.  * relies on machines being made in ascending order and that they are
  598.  * CONTIGUOUS.    Change it and you will have to rewrite DUPMACHINE (kludge
  599.  * that it admittedly is)
  600.  */
  601.  
  602. int mkstate( sym )
  603. int sym;
  604.  
  605. {
  606.     if ( ++lastnfa >= current_mns )
  607.     {
  608.         if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
  609.             lerrif( "input rules are too complicated (>= %d NFA states)",
  610.             current_mns );
  611.  
  612.         ++num_reallocs;
  613.  
  614.         firstst = reallocate_integer_array( firstst, current_mns );
  615.         lastst = reallocate_integer_array( lastst, current_mns );
  616.         finalst = reallocate_integer_array( finalst, current_mns );
  617.         transchar = reallocate_integer_array( transchar, current_mns );
  618.         trans1 = reallocate_integer_array( trans1, current_mns );
  619.         trans2 = reallocate_integer_array( trans2, current_mns );
  620.         accptnum = reallocate_integer_array( accptnum, current_mns );
  621.         assoc_rule = reallocate_integer_array( assoc_rule, current_mns );
  622.         state_type = reallocate_integer_array( state_type, current_mns );
  623.     }
  624.  
  625.     firstst[lastnfa] = lastnfa;
  626.     finalst[lastnfa] = lastnfa;
  627.     lastst[lastnfa] = lastnfa;
  628.     transchar[lastnfa] = sym;
  629.     trans1[lastnfa] = NO_TRANSITION;
  630.     trans2[lastnfa] = NO_TRANSITION;
  631.     accptnum[lastnfa] = NIL;
  632.     assoc_rule[lastnfa] = num_rules;
  633.     state_type[lastnfa] = current_state_type;
  634.  
  635.     /* fix up equivalence classes base on this transition.    Note that any
  636.      * character which has its own transition gets its own equivalence class.
  637.      * Thus only characters which are only in character classes have a chance
  638.      * at being in the same equivalence class.    E.g. "a|b" puts 'a' and 'b'
  639.      * into two different equivalence classes.    "[ab]" puts them in the same
  640.      * equivalence class (barring other differences elsewhere in the input).
  641.      */
  642.  
  643.     if ( sym < 0 )
  644.     {
  645.         /* we don't have to update the equivalence classes since that was
  646.          * already done when the ccl was created for the first time
  647.          */
  648.     }
  649.  
  650.     else
  651.         if ( sym == SYM_EPSILON )
  652.             ++numeps;
  653.  
  654.     else
  655.     {
  656.         if ( useecs )
  657.             mkechar( sym, nextecm, ecgroup );
  658.     }
  659.  
  660.     return ( lastnfa );
  661. }
  662.  
  663.  
  664. /* mkxtion - make a transition from one state to another
  665.  *
  666.  * synopsis
  667.  *
  668.  *     mkxtion( statefrom, stateto );
  669.  *
  670.  *       statefrom - the state from which the transition is to be made
  671.  *       stateto     - the state to which the transition is to be made
  672.  */
  673.  
  674. mkxtion( statefrom, stateto )
  675. int statefrom, stateto;
  676.  
  677. {
  678.     if ( trans1[statefrom] == NO_TRANSITION )
  679.         trans1[statefrom] = stateto;
  680.  
  681.     else
  682.         if ( (transchar[statefrom] != SYM_EPSILON) ||
  683.             (trans2[statefrom] != NO_TRANSITION) )
  684.             flexfatal( "found too many transitions in mkxtion()" );
  685.  
  686.     else
  687.     { /* second out-transition for an epsilon state */
  688.         ++eps2;
  689.         trans2[statefrom] = stateto;
  690.     }
  691. }
  692.  
  693. /* new_rule - initialize for a new rule
  694.  *
  695.  * synopsis
  696.  *
  697.  *     new_rule();
  698.  *
  699.  * the global num_rules is incremented and the any corresponding dynamic
  700.  * arrays (such as rule_type[]) are grown as needed.
  701.  */
  702.  
  703. new_rule()
  704.  
  705. {
  706.     if ( ++num_rules >= current_max_rules )
  707.     {
  708.         ++num_reallocs;
  709.         current_max_rules += MAX_RULES_INCREMENT;
  710.         rule_type = reallocate_integer_array( rule_type, current_max_rules );
  711.         rule_linenum =
  712.             reallocate_integer_array( rule_linenum, current_max_rules );
  713.     }
  714.  
  715.     if ( num_rules > MAX_RULE )
  716.         lerrif( "too many rules (> %d)!", MAX_RULE );
  717.  
  718.     rule_linenum[num_rules] = linenum;
  719. }
  720.  
  721.